P5451 [THUPC2018]密码学第三次小作业

如果你做过 P4358 [CQOI2016]密钥破解 ,那么你基本上就凉了。

这道题跟背景没有任何关系。

注意到二元不定方程: xe1+ye2=(e1,e2)=1xe1+ye2=(e1,e2)=1

又因为 m=m1=mxe1+ye2=(me1)x(me2)y=c1xc2ym = m^1 = m^{xe1+ye2}= (m^{e1})^x(m^{e2})^y={c_1}^x{c_2}^y

那么:

mc1xc2ymodNm\equiv{c_1}^x{c_2}^y \mod N

可以用扩欧求出一组特解 (x,y)(x',y')

当指数小于零时用逆元代替。

#include <cstdio>
using namespace std; 
#define LL long long

template<typename _T>
void Read( _T &x ) {
	x = 0; int f = 1;
	char s = getchar( );
	for( ; s < '0' || s > '9' ; s = getchar( ) ) f = s == '-' ? -f : f;
	for( ; s >= '0' && s <= '9' ; s = getchar( ) ) x = x * 10 + s - '0';
	x *= f;
}
template<typename _T>
void Write( _T x ) {
	if( x < 0 ) putchar( '-' ) , x = -x;
	if( x >= 10 ) Write( x / 10 );
	putchar( x % 10 + '0' );
}

LL N , c1 , c2 , e1 , e2;
LL x , y;

LL Exgcd( LL a , LL b , LL &x , LL &y ) {
	if( !b ) {
		x = 1 , y = 0;
		return a;
	}
	LL r = Exgcd( b , a % b , y , x );
	y -= ( a / b ) * x;
	return r; 
} 
LL Inv( LL x , LL p ) {
	LL u , v;
	Exgcd( x , p , u , v );
	return ( u % p + p ) % p;
}
LL Quick_mul( LL x , LL po , LL Mod ) {
	LL Ans = 0;
	for( ; po ; po >>= 1 , x = ( x + x ) % Mod )
		if( po & 1 ) Ans = ( Ans + x ) % Mod;
	return Ans;	
}
LL Quick_pow( LL x , LL po , LL Mod ) {
	if( po < 0 ) x = Inv( x , Mod ) , po = -po;
	
	LL Ans = 1;
	for( ; po ; po >>= 1 , x = Quick_mul( x , x , Mod ) )
		if( po & 1 ) Ans = Quick_mul( Ans , x , Mod );
	return Ans;
}


int main( ) {
//	freopen("D.in","r",stdin);
//	freopen("D.out","w",stdout);

	int t; Read( t );
	while( t -- ) {
		Read( c1 ) , Read( c2 ) , Read( e1 ) , Read( e2 ) , Read( N );
		Exgcd( e1 , e2 , x , y );
		Write( Quick_mul( Quick_pow( c1 , x , N ) , Quick_pow( c2 , y , N ) , N ) ) , putchar('\n');
	}
	return 0;
}